import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author 03010570
 * @date 2020/07/02
 * describe:    LeetCode: 378、有序矩阵中第 K 小 的元素    https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
 * <p>
 * 看到题目两种思路：
 * 1、构建使用一个大小为 K 的大顶堆，返回大顶堆堆顶元素
 * 2、利用 有序矩阵的特性，类似 BFS 的思路进行查找
 */
public class LeetCode_378 {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1, 5, 9},
                {10, 11, 13},
                {12, 13, 15}};
        int k=8;
        System.out.println(kthSmallest(matrix,k));
    }


    /**
     *  做一次 二分
     * @param matrix
     * @param k
     * @return
     */
    public static int kthSmallest2(int[][] matrix, int k) {

        return 0;
    }



        /**
         * Method 1 : 构建使用 大小为 K 的大顶堆
         *
         * @param matrix
         * @param k
         * @return
         */
    public static int kthSmallest(int[][] matrix, int k) {
        int rows = matrix.length;
        int columns = matrix[0].length;
        PriorityQueue<Integer> heap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if(heap.size() !=k){
                    heap.offer(matrix[i][j]);
                }else{
                    if(heap.peek() > matrix[i][j]){
                        heap.poll();
                        heap.offer(matrix[i][j]);
                    }
                }

            }
        }
        return heap.peek();
    }
}
